package acwing._2LanQiao._7Greedy;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._2LanQiao._7Greedy
 * @File : Q1239.java
 * @Author : WangRuoyu
 * @Date : 2023/3/20 14:43
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Q1239 {
    static long res = 1;
    static final int MOD = 1000000009;
    static Integer[] nums;

    static void mul(int l, int r) {
        for (int i = l; i <= r; ++i) {
            res *= nums[i];
            if (res > 0) {
                res %= MOD;
            } else {
                res = -((-res) % MOD);
            }
        }
        System.out.println(res);
    }

    static void mul(int l, int r, int start, int skip) {
        res = start;
        for (int i = l; i <= r; ++i) {
            if (nums[i] == skip) {
                continue;
            }
            res *= nums[i];
            if (res > 0) {
                res %= MOD;
            } else {
                res = -((-res) % MOD);
            }
        }
        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] words = br.readLine().split(" ");

        int n = Integer.parseInt(words[0]);
        int k = Integer.parseInt(words[1]);

        nums = new Integer[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = Integer.parseInt(br.readLine());
        }

        if (k == n) { // 如果k等于n，全选
            mul(0, n - 1);
            return;
        }

        Arrays.sort(nums, (o1, o2) -> Math.abs(o1) - Math.abs(o2)); // 按照绝对值排序

        int maxPositive = 0;
        int maxNegative = 0;
        int negativeNum = 0;

        for (int i = n - k; i < n; ++i) { // 统计后k个数字负数数量，还有在后k个数中绝对值最小的正数和负数
            if (nums[i] > 0 && maxPositive == 0) {
                maxPositive = nums[i];
            } else if (nums[i] < 0) {
                negativeNum++;
                if (maxNegative == 0) {
                    maxNegative = nums[i];
                }
            }
        }

        if (negativeNum == 0) { // 若后k个数全是正数，直接计算
            mul(n - k, n - 1);
            return;
        } else if (negativeNum == k) { // 若后k个数全是负数，分情况
            if (k % 2 == 1) { // k 为奇数，则寻找前n-k个数中绝对值最大的正数
                int minPositive = 0;
                for (int i = n - k - 1; i >= 0; --i) {
                    if (nums[i] > 0) {
                        minPositive = nums[i];
                        break;
                    }
                }
                if (minPositive == 0) { //若没有正数，且k为奇数，则求前k个数之积
                    mul(0, k - 1);
                } else { //若有正数，求该正数与后k-1个数之积
                    mul(n - k + 1, n - 1, minPositive, 0);
                }
            } else { // k 为偶数数，直接计算
                mul(n - k, n - 1);
            }
            return;
        }

        if (negativeNum % 2 == 0) { // 若后k个数中有偶数个负数，则直接计算
            mul(n - k, n - 1);
        } else { // 若后k个数中有奇数个负数，则寻找前n-k个数中绝对值最大的正数和负数和后k个数中绝对值最小的正数和负数，比较两正数之积和两负数之积
            int minPositive = 0;
            int minNegative = 0;
            for (int i = n - k - 1; i >= 0; --i) {
                if (nums[i] > 0 && minPositive == 0) {
                    minPositive = nums[i];
                    if (minNegative != 0) {
                        break;
                    }
                } else if (nums[i] < 0 && minNegative == 0) {
                    minNegative = nums[i];
                    if (minPositive != 0) {
                        break;
                    }
                }
            }
            long pos = (long) maxPositive * (long) minPositive;
            long neg = (long) maxNegative * (long) minNegative;
            if (pos > neg) {
                mul(n - k, n - 1, minPositive, maxNegative);
            } else {
                mul(n - k, n - 1, minNegative, maxPositive);
            }
        }
    }
}